
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

class Solution
{
public:
    vector<vector<int>> threeSum(vector<int>& nums)
    {
        int sz = nums.size();
        vector<vector<int>> vv;

        vv.reserve(sz - 3 + 1);
        sort(nums.begin(), nums.end());

        for (int i = 0; i < sz; ++i)
        {
            if (nums[i] > 0)
                break;

            int goal = -nums[i];
            int lf = i + 1, rt = sz-1;
            while (lf < rt)
            {
                if (nums[lf] + nums[rt] == goal)
                {
                    vv.push_back({ nums[i], nums[lf++], nums[rt--] });

                    while (lf < rt && nums[lf] + nums[rt] == goal)
                    {
                        vv.push_back({ nums[i], nums[lf++], nums[rt--] });
                    }
                }
                else if (nums[lf] + nums[rt] > goal)
                {
                    --rt;
                }
                else
                {
                    ++lf;
                }
            }
        }

        return vv;
    }

    int compareVersion1(string v1, string v2)
    {
        int beg1 = 0, end1 = 0, sz1 = v1.size();
        int beg2 = 0, end2 = 0, sz2 = v2.size();

        for (end1 = 0, end2 = 0; end1 < sz1 || end2 < sz2;)
        {
            int a = 0, b = 0;

            _func(beg1, end1, a, sz1, v1);
            _func(beg2, end2, b, sz2, v2);

            if (a != b)
                return a > b ? 1 : -1;
        }

        return 0;
    }

    int compareVersion2(string v1, string v2)
    {
        int i = 0, sz1 = v1.size();
        int j = 0, sz2 = v2.size();

        for (i = j = 0; i < sz1 || j < sz2; ++i, ++j)
        {
            unsigned a = 0, b = 0;

            while (i < sz1 && '.' != v1[i])
            {
                a = a * 10 + (v1[i] - '0');
                ++i;
            }

            while (j < sz2 && '.' != v2[j])
            {
                b = b * 10 + (v2[j] - '0');
                ++j;
            }

            if (a != b)
                return a > b ? 1 : -1;
        }

        return 0;
    }

private:
    void _func(int& beg, int& end, int& no, const int& sz, const string& s)
    {
        if (end >= sz)
            no = 0;
        else
        {
            while (end < sz && '.' != s[end])
            {
                ++end;
            }
            no = stoi(s.substr(beg, end - beg));
            ++end;
            beg = end;
        }
    }
};

void Test1()
{
    vector<int> v = {-1,0,1,2,-1,-4};

    Solution().threeSum(v);
}

int main()
{
    Test1();

	return 0;
}